package backtracking.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author bruin_du
 * @description 机器人的运动范围
 * @date 2022/5/28 8:10
 **/
public class Offer13_MovingCount {
    public int movingCount(int m, int n, int k) {
        //方法一：深度优先遍历，递归
//        boolean[][] arr = new boolean[m][n];
//        return dFS(0,0,m,n,arr,k);

        //方法二：广度优先遍历
        return bFS(m,n,k);
    }

    private int bFS(int m, int n, int k) {
        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] arr = new boolean[m][n];
        queue.offer(new int[]{0,0});
        int ret = 0;
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int i = tmp[0],j = tmp[1];
            if(arr[i][j]) continue;
            arr[i][j] = true;
            ret++;
            if(i + 1 < m && !judge(i + 1,j,k) && !arr[i + 1][j]) queue.offer(new int[]{i + 1,j});
            if(j + 1 < n && !judge(i,j + 1,k) && !arr[i][j + 1]) queue.offer(new int[]{i,j + 1});
        }
        return ret;
    }

    private int dFS(int i, int j, int m, int n,boolean[][] arr, int k) {
        if(i >= m || j >= n || judge(i,j,k)|| arr[i][j]) return 0;
        arr[i][j] = true;
        return dFS(i + 1,j,m,n,arr,k) + dFS(i, j + 1,m,n,arr, k) + 1;
    }

    private boolean judge(int m, int n, int k) {
        int sum = 0;
        while(m != 0){
            sum += m % 10;
            m /= 10;
        }
        while(n != 0){
            sum += n % 10;
            n /= 10;
        }
        return sum > k;
    }
}
